package com.sheng.leetcode.year2022.month07.day18;

import org.junit.Test;

import java.util.*;

/**
 * @author liusheng
 * @date 2022/07/18
 *
 * 749. 隔离病毒
 *
 * 病毒扩散得很快，现在你的任务是尽可能地通过安装防火墙来隔离病毒。
 * 假设世界由 m x n 的二维矩阵 isInfected 组成， isInfected[i][j] == 0 表示该区域未感染病毒，
 * 而  isInfected[i][j] == 1 表示该区域已感染病毒。可以在任意 2 个相邻单元之间的共享边界上安装一个防火墙（并且只有一个防火墙）。
 * 每天晚上，病毒会从被感染区域向相邻未感染区域扩散，除非被防火墙隔离。现由于资源有限，
 * 每天你只能安装一系列防火墙来隔离其中一个被病毒感染的区域（一个区域或连续的一片区域），且该感染区域对未感染区域的威胁最大且 保证唯一 。
 * 你需要努力使得最后有部分区域不被病毒感染，如果可以成功，那么返回需要使用的防火墙个数;
 * 如果无法实现，则返回在世界被病毒全部感染时已安装的防火墙个数。
 *
 * 示例 1：
 * 输入: isInfected = [[0,1,0,0,0,0,0,1],[0,1,0,0,0,0,0,1],[0,0,0,0,0,0,0,1],[0,0,0,0,0,0,0,0]]
 * 输出: 10
 * 解释:一共有两块被病毒感染的区域。
 * 在第一天，添加 5 墙隔离病毒区域的左侧。病毒传播后的状态是:
 * 第二天，在右侧添加 5 个墙来隔离病毒区域。此时病毒已经被完全控制住了。
 *
 * 示例 2：
 * 输入: isInfected = [[1,1,1],[1,0,1],[1,1,1]]
 * 输出: 4
 * 解释: 虽然只保存了一个小区域，但却有四面墙。
 * 注意，防火墙只建立在两个不同区域的共享边界上。
 *
 * 示例 3:
 * 输入: isInfected = [[1,1,1,0,0,0,0,0,0],[1,0,1,0,1,1,1,1,1],[1,1,1,0,0,0,0,0,0]]
 * 输出: 13
 * 解释: 在隔离右边感染区域后，隔离左边病毒区域只需要 2 个防火墙。
 *
 * 提示:
 * m == isInfected.length
 * n == isInfected[i].length
 * 1 <= m, n <= 50
 * isInfected[i][j] is either 0 or 1
 * 在整个描述的过程中，总有一个相邻的病毒区域，它将在下一轮 严格地感染更多未受污染的方块 
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/contain-virus
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class LeetCode0749 {

    @Test
    public void test01() {
        int[][] isInfected = {{0,1,0,0,0,0,0,1},{0,1,0,0,0,0,0,1},{0,0,0,0,0,0,0,1},{0,0,0,0,0,0,0,0}};
//        int[][] isInfected = {{1,1,1},{1,0,1},{1,1,1}};
//        int[][] isInfected = {{1,1,1,0,0,0,0,0,0},{1,0,1,0,1,1,1,1,1},{1,1,1,0,0,0,0,0,0}};
        System.out.println(new Solution().containVirus(isInfected));
    }

}
//class Solution {
//    public int containVirus(int[][] isInfected) {
//        return 0;
//    }
//}

//根据题意，我们可以按天进行模拟，设计函数 getCnt 用于返回当天会被安装的防火墙数量，
//在 getCnt 内部我们会进行如下操作：
//找出当天「对未感染区域的威胁最大」的区域，并将该区域进行隔离（将 1 设置为 −1）；
//对其他区域，进行步长为 1 的感染操作。
//考虑如何实现 getCnt：我们需要以「连通块」为单位进行处理，因此每次的 getCnt 操作，
//我们先重建一个与矩阵等大的判重数组 vis，对于每个 g[i][j] = 1 且未被 vis[i][j] 标记为 True 的位置进行搜索，搜索过程使用 BFS 实现。
//在 BFS 过程中，我们除了统计该连通块所需要的防火墙数量 b 以外，
//还需要额外记录当前连通块中 1 的点集 s1（简称为原集，含义为连通块的格子集合），
//以及当前连通块相邻的 0 的点集 s2（简称为扩充集，含义为将要被感染的格子集合）。
//根据题意，在单次的 getCnt 中，我们需要在所有连通块中取出其 s2 大小最大（对未感染区域的威胁最大）的连通块进行隔离操作，
//而其余连通块则进行扩充操作。
//因此我们可以使用两个变量 max 和 ans 分别记录所有 s2 中的最大值，以及取得最大 s2 所对应连通块所需要的防火墙数量，
//同时需要使用两个数组 l1 和 l2 分别记录每个连通块对应的「原集」和「扩充集」，方便我们后续进行「隔离」和「感染」。
//
class Solution {
    /**
     * g：传进来的原数组
     * n：g.length
     * m：g[0].length
     * ans：返回值，代表添加的防火墙的数量
     * dirs：病毒的4种走向，上下左右
     * vis：
     */
    int[][] g;
    int n, m, ans;
    int[][] dirs = new int[][]{{1,0},{-1,0},{0,1},{0,-1}};
    boolean[][] vis;
    //求需要安装的防火墙的数量
    int search(int _x, int _y, Set<Integer> s1, Set<Integer> s2) {
        //返回值
        int ans = 0;
        Deque<int[]> d = new ArrayDeque<>();
        //将当前位置标记为true
        vis[_x][_y] = true;
        d.addLast(new int[]{_x, _y});
        s1.add(_x * m + _y);
        while (!d.isEmpty()) {
            int[] info = d.pollFirst();
            int x = info[0], y = info[1];
            for (int[] di : dirs) {
                int nx = x + di[0], ny = y + di[1], loc = nx * m + ny;
                if (nx < 0 || nx >= n || ny < 0 || ny >= m || vis[nx][ny]) {
                    continue;
                }
                if (g[nx][ny] == 1) {
                    s1.add(loc);
                    vis[nx][ny] = true;
                    d.addLast(new int[]{nx, ny});
                } else if (g[nx][ny] == 0) {
                    s2.add(loc);
                    ans++;
                }
            }
        }
        return ans;
    }
    //返回当天会被安装的防火墙数量
    int getCnt() {
        //新增一个与矩阵等大的判重数组，等价于vis = new boolean[g.length][g[0].length]
        //标记为true代表已经进行搜索
        vis = new boolean[n][m];
        //max：被感染的格子的最大数量，ans：所需要的防火墙的数量
        int max = 0, ans = 0;
        // l1: 每个连通块的点集 s2: 每个连通块的候选感染点集
        List<Set<Integer>> l1 = new ArrayList<>(), l2 = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                //循环当前数组的所有点，如果当前点是病毒所在点，并且未被vis标记为true
                if (g[i][j] == 1 && !vis[i][j]) {
                    // s1: 当前连通块的点集（即为当前连通块中1的点集合） s2: 当前连通块的候选感染点集（即为当前连通块中相邻的0的点集合，将要被感染的格子）
                    Set<Integer> s1 = new HashSet<>(), s2 = new HashSet<>();
                    //b代表以s1为中心圈起来需要的防火墙的数量，a代表今晚被感染的格子的数量
                    int b = search(i, j, s1, s2), a = s2.size();
                    //如果被感染的数量大于之前的最大值，则将a赋值给max，并令今晚要安装的防火墙的数量等于b
                    if (a > max) {
                        max = a; ans = b;
                    }
                    l1.add(s1); l2.add(s2);
                }
            }
        }
        //对未感染区域威胁最大的部分进行隔离操作
        for (int i = 0; i < l2.size(); i++) {
            for (int loc : l2.get(i).size() == max ? l1.get(i) : l2.get(i)) {
                int x = loc / m, y = loc % m;
                g[x][y] = l2.get(i).size() == max ? -1 : 1;
            }
        }
        return ans;
    }
    public int containVirus(int[][] _g) {
        g = _g;
        n = g.length; m = g[0].length;
        //循环一次就是一晚上
        while (true) {
            //cnt当天会被安装的防火墙的数量
            int cnt = getCnt();
            //为零时，代表病毒已经被控制住了，结束循环
            if (cnt == 0) {
                break;
            }
            //ans代表总安装的防火墙数量
            ans += cnt;
        }
        //返回
        return ans;
    }
}
//
//作者：AC_OIer
//链接：https://leetcode.cn/problems/contain-virus/solution/by-ac_oier-l9ya/
//来源：力扣（LeetCode）
//著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
//
